#include"Sort.h"
void Arrprint(int* arr, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void insertsort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int emd = i - 1;
		while (emd >= 0)
		{
			if (arr[emd] > arr[emd + 1])
			{
				int tmp = arr[emd + 1];
				arr[emd + 1] = arr[emd];
				arr[emd] = tmp;
				emd --;
			}
			else
			{
				break;
			}
		}
	}
}
void HillSort(int* arr, int n)
{
	int gap = 3;
	int begine = 0;
	for (int i = begine; i < n - gap; i ++)
	{
		int emd = i;
		while (emd >= 0)
		{
			if (arr[emd] > arr[emd + gap])
			{
				int tmp = arr[emd + gap];
				arr[emd + gap] = arr[emd];
				arr[emd] = tmp;
				emd -= gap;
			}
			else
			{
				break;
			}
		}
	}
	insertsort(arr, n);
}